1. Field of the Invention
The invention relates to image processing methods for reducing noise in a sampled image. More specifically, the invention pertains to an image processing method which reduces noise while minimizing unintended distortion of image features.
2. Description Relative to the Prior Art
Pictures generated by an image processing method often display artifacts introduced by the processing method itself. Such artifacts may mask the benefits obtained by processing the image. This invention pertains to the suppression of a particular class of artifacts: the introduction of what appear to be "edges" into places--like smooth facial features--where no such edges existed in the original image. To better describe the invention it is necessary to review certain aspects of known image processing technology.
In known image processing methods, every image signal is replaced by a modified value, based on the values of the image signals from a surrounding field of image elements. The signals from the surrounding field are used to form a number of different linear combinations each of which represents a different component of the image structure within the field. In a typical method, most of the combinations represent the detail within the field. Each detail-sensitive combination represents a difference among local image signals and tends to vanish in the absence of a particular kind of image detail. Noise is reduced by modifying the detailsensitive combinations such that, for example, the value of a combination is lowered or set to zero wherever a particular kind of image detail is not present.
One kind of method for reducing noise is based on transformation of the image. Such a method may use--for the surrounding field of image elements--the signals from all of the image elements constituting the image, as described by Agrawal and Jain (in "Bandwidth Compression of Noisy Images," Computer and Electronic Engineering, Vol. 2, 1975, pp. 275-284) and Keshavan et al. (in "Application of Orthogonal Transforms in the Enhancement of Images in the Presence of Additive Noise," Computer and Electronic Engineering, Vol. 4, 1977, pp. 279-295). For a typical image, such a transformation carries out direct and inverse transform computations on a large array of data. It is also known to divide the image into adjacent sub-images or blocks of image elements in order to facilitate processing. (See "Transform Picture Coding," by P. A. Wintz, Proceedings of the IEEE, Vol. 60, No. 7, July 1972, pp. 809-820.) Processing each block independently reduces the computation load and the problem of managing large arrays of data.
In a transformation method, each block of image elements is treated as a superposition of a number of predetermined, basic patterns. These patterns are derived from a set of independent functions characteristic of the transform. Each pattern is numerically weighted by a factor (hereinafter called a transform coefficient signal) calculated from a linear combination of the image signals. The magnitude of each transform coefficient signal determines the contribution of the corresponding pattern to the total sub-image or block. The transform coefficient signals of all of these patterns--for all the blocks--thus constitute the original image in its transformed condition. The image (in its original condition) may be recovered by replacing the image signal of each element by a particular linear combination of the transform coefficient signals.
Numerous known transforms may be used in a transformation method for reducing noise, including (but not to be limited to) the Fourier, cosine, sine, Walsh-Hadamard, Haar, slant or Karhunen-Loeve transforms. These transforms are conventional and well known to those of ordinary skill in this art. For further information, reference is made to Digital Image Processing by W. K. Pratt (John Wiley & Sons, New York, 1978) and especially chapter 10 thereof, "Two-Dimensional Unitary Transforms" and the bibliographic references cited therein. Much of the description accompanying the present patent specification is with reference to the Walsh-Hadamard transform, which is particularly useful because of its simplicity of application to digital design.
As an example of a transformation, FIG. 1 shows the predetermined Walsh-Hadamard patterns which, superimposed in weighted combination, represent the light values of any 2 by 2 field of the original image. (Light value, as used throughout this patent application, shall mean any image-related characteristic--e.g., lightness, brightness, density, hue, and the like--that can be expressed in a form suitable for image processing.) Each pattern has four square elements, which may either be black or white. The weight of each pattern corresponds to the relative presence of that pattern in a particular 2 by 2 field of the original image. For example, if the light values of a 2 by 2 field of image elements are represented as a matrix of four image signals a.sub.ij, ##EQU1## and the weighting factors for the Walsh-Hadamard Patterns are represented as a matrix of four coefficient signals c.sub.iJ, ##EQU2## then these coefficient signals are generated from the image signals in four arithmetic operations, as follows. EQU c.sub.11 =a.sub.11 +a.sub.12 +a.sub.21 +a.sub.22 EQU c.sub.12 =a.sub.11 -a.sub.12 +a.sub.21 -a.sub.22 EQU c.sub.21 =a.sub.11 +a.sub.12 -a.sub.21 -a.sub.22 EQU c.sub.22 =a.sub.11 -a.sub.12 -a.sub.21 +a.sub.22
By inspecting the patterns in FIG. 1 with reference to these arithmetic operations, it can be seen that these operations correspond to having each black square represent a multiplication by +1 on the signal from a corresponding image element and each white square represent a multiplication by -1. In this connection, FIG. 2 is an abbreviated way of listing the arithmetic operations necessary to generate the linear combinations constituting the matrix of coefficient signals c.sub.ij. The .+-.1 multipliers mentioned above are grouped into arrays of four multipliers, each corresponding in position to the image element, and signal, they operate upon. Four arrays are provided corresponding to the four arithmetic operations mentioned above for generating the four coefficient signals. The array composed of four +1 multipliers generates an average signal (the c.sub.11 coefficient signal) over the 2 by 2 area. The other three arrays generate difference signals in response to differences in light value between image elements. These differences represent image gradients among image elements within the 2 by 2 area; in terms of the arithmetic operations for generating them, they are a function of one zero crossing along horizontal and/or vertical directions, i.e., no more than one transition from positive to negative (+1 to -1) or vice versa (-1 to +1). Such signals are hereinafter referred to as first difference signals. Noise is reduced by subjecting each of the first difference coefficient signals to a modification process.
The coefficient modification process typically involves either coring or clipping. Coring is a non-linear noise reduction process that removes signal energy--presumably noise--near the average signal axis and less than a threshold; the remaining signal is then added back to the low-pass signal represented by the average coefficient signal. (See "Digital Techniques of Reducing Television Noise," by J. P. Rossi, Journal of the Society of Motion Picture and Television Engineers, March 1978, pp. 134-140.) Clipping is a complementary process that removes signal energy--presumably image detail--that is above a threshold; the remaining noise signal is then subtracted from the fullband image signal.
A regenerated, processed image of reduced noise is obtained by inverse transforming the coefficient signals, some of which may have been modified in the preceding noise reduction process. Since the Walsh-Hadamard transform is exactly invertible, the four image signals a.sub.ij can be recovered by employing the four operations represented in FIG. 2, but now with respect to the coefficient signals, as follows. EQU a.sub.11 =1/4(c.sub.11 +c.sub.12 +c.sub.21 +c.sub.22) EQU a.sub.12 =1/4(c.sub.11 -c.sub.12 +c.sub.21 -c.sub.22) EQU a.sub.21 =1/4(c.sub.11 +c.sub.12 -c.sub.21 -c.sub.22) EQU a.sub.22 =1/4(c.sub.11 -c.sub.12 -c.sub.21 +c.sub.22)
In transforming a picture divided into blocks, the determination of the block size is a function of the spatial scale of the detail to be processed. Small blocks are appropriate for high frequency (fine) detail, larger blocks for lower frequency (coarser) detail, and so on. The selection of the block size also affects the noise frequencies that are removed. If the block size is small, noise components of low spatial frequency will remain unchanged after modification of the coefficient signals and may result in a residual mottled appearance. A large block, containing a relatively large number of elements, is needed to suppress mottle. However, using only a large block not only increases the computation load, but also degrades high-frequency detail that is confined to a small area within the block. For these reasons, it is advantageous to process the image with several block sizes in a hierarchy of stages.
Commonly assigned, copending patent application Ser. No. 441,826 (entitled "Image Processing Method Using a Block Overlap Transformation Procedure," filed Nov. 15, 1982), describes a transform processing method that operates in a hierarchy of stages, each stage employing a different-sized block operating on image signals derived from a preceding stage. Each stage responds to image gradients related to the size of the block used in that stage. A small block, corresponding to a few elements of the image, detects gradients over a small image area, i.e., local image gradients. A larger block, corresponding to a relatively larger number of elements, detects gradients over a larger area, i.e., extended image gradients. In each stage, part of the original image signal is regenerated as a function of the difference between the light value of each image element and an average light value over the immediate area (i.e., the block) including that element. By additionally overlapping the blocks processed in each stage, the processed signal from each image element is the linear combination of many transform coefficient signals from each stage and from each overlapped block within each stage. Such a large number of contributions making up each processed image element assures that the processed image is generated without a characteristic block-like structure due to block transform processing.
Since the noise reduction process involves the application of a non-linear function (e.g., a threshold), some distortion of local image values may be generated as an artifact of the noise processing itself, but this is often tolerated in order to realize the desired noise reduction. Some of this distortion--that having to do with a block-like structure--is reduced by the block overlap procedure described in the heretofore cited Ser. No. 441,826. However, other distortion--like that related to the introduction of "edges"--is not adequately treated by the block overlap procedure. The problem with a block transform method--like that described in Ser. No. 441,826--is that any first difference coefficient signal capable of representing a block-wide gradient is similarly representative of segments of more extended gradients. For example, a coefficient signal generated from a block covering only a few image elements not only responds to the change of a local gradient, e.g., a low contrast edge, but also responds to a gradual change in a smooth, extended image gradient--such as is frequently found within smooth areas of scene objects. A local gradient and an extended gradient may thus look the same to a coefficient-generating operation that is coextensive with the local field of a small block. The "false edge" artifact arises when a threshold set up to distinguish low contrast detail in a local field is "falsely" triggered by a smooth, extended gradient.
The non-linear coring (or clipping) procedure is in part justified by the assumption that transition between the cored and non-cored (or clipped and non-clipped) states is mostly acceptable in a "busy" region of the image, as at an edge. The problem arises where the local and extended gradients appear the same, that is, in certain less "busy" regions of an image where the light value is changing only smoothly and slowly. In such regions the value of one or more of the detail-sensitive linear combinations derived from the smaller block will pass through its noise threshold. Because this situation activates the coring (or clipping) procedure, an abrupt discontinuity will undesirably appear in the processed image at the point where the threshold is crossed and the corresponding linear combination is undesirably modified. In less "busy" regions--like the smoothed area of an extended gradient--this transition sometimes leads to a visible artifact--much like an "edge"--and therefore is undesirable. From an aesthetic viewpoint, such artifacts particularly detract from the overall visual appeal of images reproduced by such methods. In fact, in some areas of an image such transitions may be more objectionable than the original noise component that the coefficient modification process has removed. Transform methods of which I am aware are unable to effectively deal with these types of artifacts, therefore yielding aesthetically unappealing results. My invention provides a solution for this type of problem.